package com.wzq.sort;

import java.lang.reflect.Array;
import java.util.Arrays;

public class AllSort {


    private final static int TEST_CNT = 10000;

    private static int[] getTestArr(){
        int[] arr = new int[TEST_CNT];
        for (int i=0;i<TEST_CNT;i++){
            arr[i] = (int)(Math.random()*TEST_CNT);

        }
        return arr;
    }
    private static boolean checkSort(int[] arr){

        for (int i=0;i<arr.length-1;i++){
            if(arr[i]>arr[i+1]){
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {

        int[] arr = getTestArr();
        long t1,t2;

        int[] arr1 = Arrays.copyOf(arr,arr.length);
        t1 = System.currentTimeMillis();
        bubbleSort(arr1);
        t2 = System.currentTimeMillis();
        System.out.println("bubbleSort\t"+checkSort(arr1)+"\t"+(t2-t1)+"ms");

        int[] arr2 = Arrays.copyOf(arr,arr.length);
        t1 = System.currentTimeMillis();
        selectSort(arr2);
        t2 = System.currentTimeMillis();
        System.out.println("selectSort\t"+checkSort(arr2)+"\t"+(t2-t1)+"ms");

        int[] arr3 = Arrays.copyOf(arr,arr.length);
        t1 = System.currentTimeMillis();
        insertSort(arr3);
        t2 = System.currentTimeMillis();
        System.out.println("insertSort\t"+checkSort(arr3)+"\t"+(t2-t1)+"ms");

        int[] arr4 = Arrays.copyOf(arr,arr.length);
        t1 = System.currentTimeMillis();
        mergeSort(arr4);
        t2 = System.currentTimeMillis();
        System.out.println("mergeSort\t"+checkSort(arr4)+"\t"+(t2-t1)+"ms");

    }

    public static void main1(String[] args) {

        int[] arr = new int[]{4,3,2,1,5,6};
        mergeSort(arr);
        System.out.println("niubi");
    }

    private static void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private static void bubbleSort(int[] arr){
        int len = arr.length;
        boolean flag = true;
        for (int i=1; i<len && flag; i++){
            flag = false;
            for (int j=0; j<len-i; j++){
                if(arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                    flag = true;
                }
            }
        }

    }

    private static void selectSort(int[] arr){
        int len = arr.length;
        for (int i=0; i<len; i++){
            int minIndex = i;
            for (int j=i+1; j<len; j++){
                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            if( minIndex != i){
                swap(arr,minIndex,i);
            }
        }
    }

    private static void insertSort(int[] arr){
        int len = arr.length;
        for (int i=1; i<len; i++){
            int tmp = arr[i];
            int j=i-1;
            while (j>=0 && tmp < arr[j]){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = tmp;
        }
    }


    private static void mergeSort(int[] arr){
        mergeSort1(arr,0,arr.length-1);
    }

    private static void mergeSort1(int[] arr,int start,int end){
        int start1 = start;
        int end1 = (start+end)/2;
        int start2 = (start+end)/2+1;
        int end2 = end;
        if(start<end){
            mergeSort1(arr,start1,end1);
            mergeSort1(arr,start2,end2);
            merge(arr,start1,end1,start2,end2);
        }

    }


    private static void merge(int[] arr,int start1,int end1,int start2,int end2){
        int i1 = start1;
        int i2 = start2;
        int[] mergeArr = new int[end1+end2-start1-start2+2];
        int i=0;
        while (i1<=end1 && i2<=end2){
            if(arr[i1]<arr[i2]){
                mergeArr[i++] = arr[i1++];
            }else{
                mergeArr[i++] = arr[i2++];
            }
        }
        while (i1<=end1){
            mergeArr[i++] = arr[i1++];
        }
        while (i2<=end2){
            mergeArr[i++] = arr[i2++];
        }
        i=0;
        while (start1<=end1){
            arr[start1++]=mergeArr[i++];
        }
        while (start2<=end2){
            arr[start2++]=mergeArr[i++];
        }
    }


}
